class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
	//动态规划，完全背包得思想来解决
	//定义dp数据
	vector<bool> dp(s.size()+1,false);//初始化

	//初始化
	dp[0] = true;

	//遍历dp数组
	//将字典放入set容器中排序
	unordered_set<string> wordSet(wordDict.begin(), wordDict.end());

	for (int i = 1; i <= s.size(); i++)
	{

		for (int j = 0; j < i; j++)
		{
			string word = s.substr(j, i - j); //使用j不断截取区间内得子串
			if (wordSet.find(word) != wordSet.end() && dp[j])
			{
				dp[i] = true;
			}
		}

	}

	return dp[s.size()];
    }
};